package cn.xiaolang.function.sort_algorithm;

/**
 * 插入排序算法
 *
 * @author fuhw/DeanKano
 * @date 2018-11-28
 */
public class InsertSort extends AbstractSort {

	/**
	 * 把n个待排序的元素,分为有序表和无序表
	 * <ul>1.起初,有序表为第一个元素,无序表为n-1个元素</ul>
	 * <ul>2.排序过程,从无序表中取出一个元素,插入到有序表到适当位置</ul>
	 * <ul>3.重复n-1次可完成排序</ul>
	 */
	@Override
	public void sort(int[] a) {
		// 获取数组长度
		int arrLen = a.length;
		int insertEle;
		// 循环无序表
		for (int i = 1; i < arrLen; i++) {
			insertEle = a[i];//取一元素
			int j = i - 1;//和有序表中到元素比对
			while (j >= 0 && a[j] > insertEle) {
				a[j + 1] = a[j];//将大于insertEle的数向后移动
				j--;
			}
			a[j + 1] = insertEle;
		}
	}
}
